// https://www.lintcode.com/problem/combination-sum-iv/my-submissions


// 法一：回溯 TLE
class Solution {
public:
    int cnt = 0;

    // 不同的顺序也算，所以不用记录start，直接从0开始遍历！！！
    // void helper(vector<int>& nums, vector<int>& tmp, int start, int sum, int target) {
    //     // if (start == nums.size()) {
    //     //     if (sum == target) {
    //     //         cnt++;
    //     //     }
    //     //     return;
    //     // } 
    //     if (sum >= target) {
    //         if (sum == target) {
    //             for (auto& t: tmp) {
    //                 cout << t << " ";
    //             }
    //             cout << endl;
    //         }
    //         return;
    //     }
    //     for (int i = start; i < nums.size(); ++i) {
    //         // if (nums[i])
    //         sum += nums[i];
    //         tmp.push_back(nums[i]);
    //         // helper(nums, i + 1, sum, target);
    //         helper(nums, tmp, i, sum, target); //可重复，所以不加一。更改退出条件
    //         sum -= nums[i];
    //         tmp.pop_back();
    //     }
    // }

    void helper(vector<int>& nums, int sum, int target) {
        if (sum >= target) {
            if (sum == target) {
                cnt++;
            }
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            // if (sum + nums[i] > target) return; 这边不需要去重没有排序，所以不能return！！！
            if (sum + nums[i] > target) continue;
            sum += nums[i];
            helper(nums, sum, target);
            sum -= nums[i];
        }
    }

    int combinationSum4(vector<int>& nums, int target) {
        helper(nums, 0, target);
        return cnt;
    }
};

// 法二：组合背包问题：背包中的物品要考虑顺序
// https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/yi-pian-wen-zhang-chi-tou-bei-bao-wen-ti-a7dd/
// 如果允许负数出现，则必须限制排列的最大长度，避免出现无限长度的排列，才能计算排列数。
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> rec(target + 1, 0);
        rec[0] = 1;
        // 排列顺序没考虑，是针对每个数字，考虑是否放进背包
        // for (int i = 0; i < n; ++i) {
        //     for (int j = nums[i]; j <= target; ++j) {
        //         rec[j] += rec[j - nums[i]]; 
        //     }
        // }
        // 可以理解为，对每一个target，每种数字作为结尾的情况都考虑一遍
        for (int i = 1; i <= target; ++i) {
            for (int j = 0; j < n; ++j) {
                // if (i >= nums[j]) rec[i] += rec[i - nums[j]];
                if (i >= nums[j] && rec[i - nums[j]] < INT_MAX - rec[i]) 
                    rec[i] += rec[i - nums[j]];
            }
        }
        return rec[target];
    }
};